package java_heap;

import java.util.ArrayList;

public class MinHeap {
    private ArrayList<Long> data;
    public MinHeap(){
        data = new ArrayList<>();
    }
    public MinHeap(int capacity){
        data = new ArrayList<>(capacity);
    }
    // 返回堆中的元素个数
    public int size(){
        return data.size();
    }
    // 返回堆中的层数
    public int getStorey(){
        int size = this.size();
        int storey = 1;
        while (true){
            if(size < 2) return storey;
            storey++;
            size = size / 2;
        }
    }
    // 打印
    private final String DIVIDER = "___";
    public void toPrint(){
        int storey = this.getStorey();
        for (int i = 1; i <= storey; i++) {
            // 分割
            for (int z = 0; z <= storey - i; z++) {System.out.print(DIVIDER);}
            // 计算长
            int size = Double.valueOf(Math.floor(Math.pow(2,i-1))).intValue();
            // 行内容填充
            for (int j = 0; j < size &&  size + j - 1 < data.size(); j++) {
                System.out.print("" + String.format("%02d", data.get(size + j - 1)) + "");
                // 分割
                for (int z = 0; z <= storey - i; z++) {System.out.print(DIVIDER);}
            }
            System.out.print("\n");
        }
    }
    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty(){
        return data.isEmpty();
    }
    // 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
    private int parent(int index){
        return (index - 1) / 2;
    }
    // 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index){
        return index * 2 + 1;
    }
    // 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index){
        return index * 2 + 2;
    }
    // 交换传入的索引两个位置的元素值
    public void swap(int i, int j) {
        if (i < 0 || i >= size() || j < 0 || j >= size())
            throw new IllegalArgumentException("Index is illegal.");
        Long temp = this.data.get(i);
        this.data.set(i, this.data.get(j));
        this.data.set(j, temp);
    }
    // 堆中添加元素方法。
    public void add(Long e) {
        //特性1：新插入的元素首先放在数组最后，保持完全二叉树的特性
        this.data.add(e);
        siftUp(data.size() - 1);
    }
    // index 为i位置元素上浮
    private void siftUp(int i) {
        //特性2：比较插入值和其父结点的大小关系，小于父结点则用父结点替换当前值，index位置上升为父结点
        // 当上浮元素大于父亲，继续上浮。并且不能上浮到0之上
        // 直到i 等于 0 或 比 父亲节点小了。
        while (i > 0 && data.get(i).compareTo(data.get(parent(i))) > 0) {
            // 数组Array中添加方法swap
            this.swap(i, parent(i));
            i = parent(i); // 这句话让i来到新的位置，使得循环可以查看新的位置是否还要大。
        }
    }
    // 寻找最小
    public Long findMin() {
        return data.get(0);
    }
    // 删除最小
    public Long extractMin() {
        Long ret = findMin();
        this.swap(0, this.size() - 1); // 0位置元素和最后一个元素互换。
        this.data.remove(data.size() - 1); // 删除此时的最后一个元素(最小值)
        siftDown(0); // 对于0处进行siftDown操作
        return ret;
    }
    // k位置元素下移
    private void siftDown(int k) {
        while(leftChild(k) < this.size()){
            int j = leftChild(k); // 在此轮循环中,data[k]和data[j]交换位置
            if( j + 1 < this.size() &&
                    data.get(j + 1).compareTo(data.get(j)) < 0 )
                j ++;
            // data[j] 是 leftChild 和 rightChild 中的最小值
            if(data.get(k).compareTo(data.get(j)) >= 0 )
                break;
            this.swap(k, j);
            k = j;
        }
    }
}
